// 使用动态规划实现最长公共子序列
// ref: 力扣1143题 https://leetcode.cn/problems/longest-common-subsequence/description

#include <vector>
#include <string>
#include <iostream>
#include <limits.h>

int longestCommonSubsequence(std::string text1, std::string text2) {
    int m = text1.length(), n = text2.length();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
    for (int i = 1; i <= m; i++) {
        char c1 = text1.at(i - 1);
        for (int j = 1; j <= n; j++) {
            char c2 = text2.at(j - 1);
            if (c1 == c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}


int main(int argc, char const *argv[]) {
    std::string word1 = "horse", word2 = "ros";

    int res = longestCommonSubsequence(word1, word2);
    std::cout << res << std::endl;

    return 0;
}